#include "include/gtest.h"
#include "../Tool/include/ILogger.h"
#include "../Tool/include/Random.h"
#include "../Tool/include/Timer.h"
#include "../Tool/include/ThreadPool.h"
#include <unordered_map>

using namespace Tool;

//空间索引
TEST(Code, SpatialGridTest)
{
	struct Point
	{
		double x;
		double y;
	};

	struct Rect
	{
		double x;
		double y;
		int w;
		int h;
	};

	std::vector<Point> points;
	std::vector<Rect> find_rect;
	Timer timer;
	int count = 500000;
	points.resize(count);
	Random random;
	double value = count * 10.0;
	for (int i = 0; i < count; ++i) 
	{
		double x = random.GetDouble(- value, value);
		double y = random.GetDouble(- value, value);
		points[i] = { x, y };
	}

	find_rect.resize(count / 10);
	for (int i = 0; i < count / 10; ++i)
	{
		double x = random.GetDouble(- value / 2, value / 2);
		double y = random.GetDouble(- value / 2, value / 2);
		int w = random.GetInt(10, count / 5);
		int h = random.GetInt(10, count / 5);
		find_rect[i] = { x, y, w, h };
	}
	LOG_INFO("测试数据生成完成，共 %d 个随机点", count);

	//普通使用
	timer.Reset();
	std::vector<Point> result;
	for (const auto& rect : find_rect)
	{
		for (const auto& p : points)
		{
			if (p.x >= rect.x && p.x <= rect.x + rect.w && p.y >= rect.y && p.y <= rect.y + rect.h)
			{
				result.push_back(p);
			}
		}
	}
	LOG_INFO("数据量: %d/%d, 不使用空间索引耗时: %.3lf", result.size(), count, timer.Elapsed());

	//使用空间索引
	result.clear();
	timer.Reset();
	std::unordered_map<std::string, std::vector<Point>> spatialGrid;
	double minX = INFINITY, maxX = -INFINITY, minY = INFINITY, maxY = -INFINITY;
	for (auto& point : points)
	{
		minX = std::min(minX, point.x);
		maxX = std::max(maxX, point.x);
		minY = std::min(minY, point.y);
		maxY = std::max(maxY, point.y);
	}
	double gradSize = std::max((maxX - minX) / 20.0, (maxY - minY) / 20.0);
	double actualSize = std::max(gradSize, 100.0);
	for (auto& point : points)
	{
		int x = static_cast<int>(point.x / actualSize);
		int y = static_cast<int>(point.y / actualSize);
		std::string key = std::to_string(x) + "," + std::to_string(y);
		spatialGrid[key].push_back(point);
	}
	for (const auto& rect : find_rect)
	{
		double rectRight = rect.x + rect.w;
		double rectBottom = rect.y + rect.h;

		int gridLeft = static_cast<int>(rect.x / actualSize);
		int gridRight = static_cast<int>(rectRight / actualSize);
		int gridTop = static_cast<int>(rect.y / actualSize);
		int gridBottom = static_cast<int>(rectBottom / actualSize);
		for (int x = gridLeft; x <= gridRight; ++x)
		{
			for (int y = gridTop; y <= gridBottom; ++y)
			{
				std::string key = std::to_string(x) + "," + std::to_string(y);
				auto it = spatialGrid.find(key);
				if (it == spatialGrid.end())
				{
					continue;
				}
				for (const auto& p : it->second) 
				{
					if (p.x >= rect.x && p.x <= rectRight && p.y >= rect.y && p.y <= rectBottom) 
					{
						result.push_back(p);
					}
				}
			}
		}
	}
	LOG_INFO("数据量: %d/%d, 使用空间索引耗时: %.3lf", result.size(), count, timer.Elapsed());
}